optinimize - SECCON 2023

#SECCON_2023 #Perrin_number

配布されたバイナリを解析すると、flagのi番目の文字を以下のように計算していることがわかった。

1. Perrin numberを用いてns[i]番目の素数pを求める

2. cs[i] ^ (p & 0xff)をflagのi番目の文字とする

1の計算には非常に時間がかかるため、適当なライブラリ（今回はprimesieveを使用した）を用いることで高速化できる。ただしPerrin numberによる素数判定では実際には素数でない数が素数として判定される場合があるため、ライブラリを使った処理に置換するだけでは計算結果が異なってしまう。そのような数はPerrin pseudoprimesとして知られているため、都度補正することで1の値を正しく求めることができた。

code:python

import string

from primesieve import *

ns = [0x000000000000004A,

0x0000000000000055,

0x000000000000006F,

0x0000000000000079,

0x0000000000000080,

0x0000000000000095,

0x00000000000000AE,

0x00000000000000BF,

0x00000000000000C7,

0x00000000000000D5,

0x0000000000000306,

0x0000000000001AC8,

0x00000000000024BA,

0x0000000000003D00,

0x0000000000004301,

0x0000000000005626,

0x0000000000006AD9,

0x0000000000007103,

0x000000000000901B,

0x0000000000009E03,

0x00000000001E5FB6,

0x000000000026F764,

0x000000000030BD9E,

0x0000000000407678,

0x00000000005B173B,

0x00000000006FE3B1,

0x000000000078EF25,

0x0000000000858E5F,

0x000000000098C639,

0x0000000000AD6AF6,

0x0000000001080096,

0x00000000018E08CD,

0x0000000001BB6107,

0x0000000001F50FF1,

0x00000000025C6327,

0x0000000002A971B6,

0x0000000002D68493,

0x000000000362F0C0,

0x0000000003788EAD,

0x0000000003CAA8ED]

cs = [0x000000000000003C,

0x00000000000000F4,

0x000000000000001A,

0x00000000000000D0,

0x000000000000008A,

0x0000000000000017,

0x000000000000007C,

0x000000000000004C,

0x00000000000000DF,

0x0000000000000021,

0x00000000000000DF,

0x00000000000000B0,

0x0000000000000012,

0x00000000000000B8,

0x000000000000004E,

0x00000000000000FA,

0x00000000000000D9,

0x000000000000002D,

0x0000000000000066,

0x00000000000000FA,

0x00000000000000D4,

0x0000000000000095,

0x00000000000000F0,

0x0000000000000066,

0x000000000000006D,

0x00000000000000CE,

0x0000000000000069,

0x0000000000000000,

0x000000000000007D,

0x0000000000000095,

0x00000000000000EA,

0x00000000000000D9,

0x000000000000000A,

0x00000000000000EB,

0x0000000000000027,

0x0000000000000063,

0x0000000000000075,

0x0000000000000011,

0x0000000000000037,

0x00000000000000D4]

pseudoprime = 271441, 904631, 16532714, 24658561, 27422714, 27664033, 46672291, 102690901, 130944133, 196075949, 214038533, 517697641, 545670533, 801123451, 855073301, 903136901, 970355431, 1091327579, 1133818561, 1235188597, 1389675541, 1502682721, 2059739221, 2304156469, 2976407809, 3273820903

flag = ''

for i in range(40):

p = nth_prime(nsi - 1)

offset = len(x for x in pseudoprime if x <= p)

p = nth_prime(nsi - 1 - offset)

f = chr(csi ^ (p & 0xff))

flag += f

print(flag)